package com.gofaraway.service.左神算法课;


/**
 * 合并两个有序链表
 * <p>
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 */
public class Code08_mergeTwoSortedList {


    public static ListNode mergeTwoSortedList(ListNode head1, ListNode head2) {

        if (head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }

        ListNode head = head1.value < head2.value ? head1 : head2;

        ListNode pre  = head;
        ListNode cur1  = head.next;
        ListNode cur2  = head == head1 ? head2 : head1;


        while (cur1 != null && cur2 != null) {
            if (cur1.value < cur2.value) {
                pre.next = cur1;
                cur1 = cur1.next;
            } else {
                pre.next = cur2;
                cur2 = cur2.next;
            }

            pre = pre.next;
        }

        pre.next = cur1 == null ? cur2 : cur1;
        return head;


    }


    static class ListNode {

        public int value;

        public ListNode next;


        public ListNode(int value) {
            this.value = value;
        }

        public ListNode() {
        }
    }
}
